package com.gyg.程序员面试金典;

/**
 * Your SortedStack object will be instantiated and called as such:
 * SortedStack obj = new SortedStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.isEmpty();
 */

import java.util.Stack;

/**
 * 面试题 03.05. 栈排序
 *
 * @author gyg
 */
public class T03_05 {
    private Stack<Integer> stack;
    private Stack<Integer> tmpStack;

    public T03_05() {
        stack = new Stack<Integer>();
        tmpStack = new Stack<Integer>();
    }

    public void push(int val) {
        //找到合适位置插入val
        while(!stack.isEmpty() && stack.peek() < val){
            tmpStack.push(stack.pop());
        }
        stack.push(val);
        //将暂存在tmpStack中的元素重新复原到stack
        while(!tmpStack.isEmpty()){
            stack.push(tmpStack.pop());
        }
    }

    public void pop() {
        if(!stack.isEmpty()){
            stack.pop();
        }
    }

    public int peek() {
        if(!stack.isEmpty()){
            return stack.peek();
        }else{
            return -1;
        }
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
}
